package quadTree;
/**
 * QuadTree.java
 * @author Kirk Roerig
 * 
 *	Spatial partitioning data structure that speeds up collision detection
 *  by only checking against objects that are in the same, or overlapping
 *  QuadTree nodes.
 */
import java.util.LinkedList;

import engine.PhysicsObject;
import engine.Vector;
import quadTree.BoundingBox.IntersectRes;

//TODO Unit Test

/*
 * @ public invariant root != null;
 * @ public invariant height > 0;
 */
public class QuadTree {
	private /*@ spec_public @*/ QuadNode root;
	/*@ spec_public @*/ int size = 0;
	/**
	 * QuadTree Constructor
	 * @param simSpace the BoundingBox that envelops the entire scene
	 * @param subdivisions the number of times to divide the scene into quadrants - 1 gives 4 areas, 2 gives 16, 3 gives 64 etc
	 */
	/*
	 * @ requires subdivisions > 0;
	 * @ requires simSpace != null;
	 * @ ensures size = 1;
	 */
	public QuadTree(BoundingBox simSpace, int subdivisions){
		root = new QuadNode(this, simSpace);
		subdivide(root, subdivisions);
		size++;
	}
	/**
	 * subdivide creates the four children for a QuadNode
	 * @param node to have children made for
	 * @param depth the maximum number of generations below this QuadNode
	 */
	private void subdivide(QuadNode node, int depth){
		float w = node.getKey().getWidth();
		float h = node.getKey().getHeight();
		
		Vector childMin = node.getKey().getULcorner();
		Vector childMax = node.getKey().getLRcorner();
		childMax = Vector.sub(childMax, childMin);
		childMax.scl(0.5f);
		childMax.add(childMin);
		
		if(depth > 0){
			for(int i = 0; i < 4; i++){
				Vector trans = new Vector((i%2)*(w/2),
										  (i/2)*(h/2));
				BoundingBox b = new BoundingBox(Vector.add(childMin, trans),
												Vector.add(childMax, trans));
				QuadNode child = new QuadNode(node, b);
				node.addChild(child);
				size++;
				subdivide(child, depth - 1);
			}
		}
	}
	/**
	 * Insert adds a PhysicsObject to the tree using the object's BoundingBox.
	 * Also, obj's parent attribute is set as a reference to the found node.
	 * @param obj the PhysicObject to be added
	 * @return the QuadNode the PhysicsObject's BoundingBox is stored in
	 */
	/*
	 * @ requires obj != null;
	 * @ ensures root.getKey().contains(obj) == IntersectRes.contains ==> /result != null;
	 */
	public QuadNode insert(PhysicsObject obj){
		BoundingBox key = obj.getBoundingBox();
		
		QuadNode destNode = findSpecific(key);
		
		if(destNode != null){
			destNode.getData().add(obj);
			obj.parent = destNode;
		}
		
		return destNode;
	}
	/**
	 * findSpecific finds the QuadNode that best matches the passed BoundingBox
	 * @param key the BoundingBox used in searching
	 * @return the QuadNode that best matches the query
	 */
	/*
	 * @ requires key != null;
	 */
	public QuadNode findSpecific(BoundingBox key){
		return findSpec(root, key);
	}
	/**
	 * findSpec, helper method for findSpecific 
	 * @param node the starting QuadNode
	 * @param key the BoundingBox to use while searching
	 * @return the QuadNode that matches the query best
	 */
	/*
	 * @ requires key != null;
	 * @ requires node != null;
	 */
	private QuadNode findSpec(QuadNode node, BoundingBox key){
		QuadNode Out = null;
		
		for(QuadNode n : node.getChildren()){
			if(n.getKey().Contains(key) == IntersectRes.contains){
				Out = findSpec(n, key);
			}
		}
		
		if(Out == null){
			return node;
		}
		else
			return Out;
	}
	/**
	 * size Returns the total number of nodes in the QuadTree
	 * @return the number of QuadNodes in the QuadTree
	 */
	/*
	 * @ ensures /result == size;
	 */
	public int size(){
		return size;
	}
	/**
	 * findIntersect finds the deepest QuadNodes in the QuadTree within the passed BoundingBox
	 * @param key the BoundingBox to be used for searching
	 * @return the path from the root to the best match, or an empty list if the BoundingBox is not in the QuadTree
	 */
	/*
	 * @ requires key != null;
	 */
	public LinkedList<QuadNode> findIntersect(BoundingBox key){
		if(root.getKey().Contains(key)==IntersectRes.contains)
			return findInter(root, key);
		else
			return new LinkedList<QuadNode>();
	}
	/**
	 * findInter finds the best match in the QuadTree for a BoundingBox
	 * @param node the QuadNode to start at
	 * @param key the BoundingBox to use while searching
	 * @return a list representation of the path from the starting QuadNode to the best match
	 */
	/*
	 * @ requires node != null;
	 * @ requires key != null;
	 * @ ensures /result.size() >= 0;
	 */
	public LinkedList<QuadNode> findInter(QuadNode node, BoundingBox key){
		LinkedList<QuadNode> Out = new LinkedList<QuadNode>();
		Out.addLast(node);	// add self to output
		
		// Iterate thru children, of node, if a child contains
		// the key, then recurse to it, checking for a better match.
		// if one is found add it to the 'Out' list.
		for(QuadNode n : node.getChildren()){
			if(n.getKey().Contains(key) == IntersectRes.contains)
				for(QuadNode m : findInter(n, key))
					Out.addLast(m);
		}
		
		return Out;
	}
	/**
	 * getAllNodes Returns a list containing all QuadNodes in the QuadTree
	 * @return the list containing the QuadNodes
	 */
	/*
	 * @ ensures /result.size() == this.size;
	 */
	public LinkedList<QuadNode> getAllNodes(){
		return getAll(root);
	}
	/**
	 * getAll creates and returns a list of all the nodes in the QuadTree including and below the passed QuadNode
	 * @param node the node to start with
	 * @return a list of all descendants in the tree 
	 */
	/*
	 * @ requires node != null;
	 */
	private LinkedList<QuadNode> getAll(QuadNode node){
		LinkedList<QuadNode> Out = new LinkedList<QuadNode>();
		Out.addLast(node); // add self to output
		
		// recurse thru children, adding all
		// descendants to the output list.
		for(QuadNode n : node.getChildren()){
			for(QuadNode m : getAll(n))
				Out.addLast(m);
		}
		
		return Out;
	}
	/**
	 * getRoot returns the root of the QuadTree
	 * @return the Quadtree's root
	 */
	/*
	 * ensures /result == this.root;
	 */
	public QuadNode getRoot() {
		return root;
	}
}
